package com.gxc.tree;

/**
 * 节点的后续节点
 * 1.节点有右孩子结点，则右孩子节点的最左节点是后续节点
 * 2.节点没有右孩子结点，节点是否是父节点的做孩子，如果是，则父节点是后续节点
 */
public class FollowUpTree {

    public static void main(String[] args) {
        TreeBean one = new TreeBean(1);
        TreeBean two = new TreeBean(2);
        TreeBean three = new TreeBean(3);
        TreeBean four = new TreeBean(4);
        TreeBean five = new TreeBean(5);
        TreeBean six = new TreeBean(6);
        TreeBean seven = new TreeBean(7);
        TreeBean eight = new TreeBean(8);

        one.left = two;
        one.right = three;

        two.left = four;
        two.right = five;
        two.parent = one;

        three.left = six;
        three.right = seven;
        three.parent = one;

        four.left = eight;
        four.parent = two;

        five.parent = two;

        six.parent = three;
        seven.parent = three;

        eight.parent = four;

        TreeBean node = followUp(six);
        System.out.println(node.value);

        node = followUp(seven);
        if (node!=null)System.out.println(node.value);
        else System.out.println("null");
    }

    private static TreeBean followUp(TreeBean node) {
        if (node == null) return null;
        //节点有右孩子结点，则右孩子节点的最左节点是后续节点
        if (node.right!=null) {
            return leftNode(node.right);
        } else {
            //节点没有右孩子结点，节点是否是父节点的做孩子，如果是，则父节点是后续节点
            while (node.parent!=null && node.parent.left!=node) {
                node = node.parent;
            }
            return node.parent;
        }
    }

    private static TreeBean leftNode(TreeBean head) {
        if (head.left == null) return head;
        while (head.left != null) {
            head = head.left;
        }
        return head;
    }

    /**
     * 创建带有父节点的树
     * @return
     */
    public static TreeBean createTree() {
        TreeBean one = new TreeBean(1);
        TreeBean two = new TreeBean(2);
        TreeBean three = new TreeBean(3);
        TreeBean four = new TreeBean(4);
        TreeBean five = new TreeBean(5);
        TreeBean six = new TreeBean(6);
        TreeBean seven = new TreeBean(7);
        TreeBean eight = new TreeBean(8);

        one.left = two;
        one.right = three;

        two.left = four;
        two.right = five;
        two.parent = one;

        three.left = six;
        three.right = seven;
        three.parent = one;

        four.left = eight;
        four.parent = two;

        five.parent = two;

        six.parent = three;
        seven.parent = three;

        eight.parent = four;
        return one;
    }
}
